package com.jz.main.io.nio;

public class MaxWeight {
        public static int maxWeightPath(int[][] matrix) {
            int rows = matrix.length;
            int cols = matrix[0].length;

            // 创建一个与原始矩阵相同大小的矩阵，用于记录到达每个位置时的最大权重
            int[][] dp = new int[rows][cols];

            // 计算第一行和第一列的最大权重，因为只有一种移动方式
            dp[0][0] = matrix[0][0];
            for (int i = 1; i < rows; i++) {
                dp[i][0] = dp[i-1][0] + matrix[i][0];
            }
            for (int j = 1; j < cols; j++) {
                dp[0][j] = dp[0][j-1] + matrix[0][j];
            }

            System.out.println();
            // 从第二行和第二列开始，计算每个位置的最大权重
            for (int i = 1; i < rows; i++) {
                for (int j = 1; j < cols; j++) {
                    // 取从上方和左方移动过来的路径中权重较大的那个
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + matrix[i][j]; // 最大权重
                    dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + matrix[i][j]; // 最小权重
                }
            }

            // 最终右下角的值即为到达右下角时的最大权重
            return dp[rows-1][cols-1];
        }

        public static void main(String[] args) {
            int[][] matrix = {
                    {1, 3, 1},
                    {1, 1, 2},
                    {4, 9, 1}
            };
            //  最大权重为16，最小为6
//            int[][] matrix = {
//                    {1, 4, 5},
//                    {2, 3, 5},
//                    {4, 9, 6}
//            };

            System.out.println("最大权重为: " + maxWeightPath(matrix));
        }

}
